import java.util.*;

/**
 * 1636. 按照频率将数组升序排序
 * https://leetcode-cn.com/problems/sort-array-by-increasing-frequency/
 */
public class Solutions_1636 {
    public static void main(String[] args) {
        int[] nums1 = {1, 1, 2, 2, 2, 3};  // output: {3, 1, 1, 2, 2, 2}
        int[] nums2 = {2, 3, 1, 3, 2};  // output: {1, 3, 3, 2, 2}
        int[] nums3 = {-1, 1, -6, 4, 5, -6, 1, 4, 1};  // output: {5, -1, 4, 4, -6, -6, 1, 1, 1}

        List<int[]> inputs = new ArrayList<>();
        inputs.add(nums1);
        inputs.add(nums2);
        inputs.add(nums3);

        for (int[] input : inputs) {
            int[] result = frequencySort(input);
            System.out.println(Arrays.toString(result));
        }
    }

    /**
     * 数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。
     */
    public static int[] frequencySort(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int[] map = new int[201];
        for (int num : nums) {
            list.add(num);
            map[num + 100] ++;
        }
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                int num1 = o1.intValue(), num2 = o2.intValue();
                int cnt1 = map[num1 + 100], cnt2 = map[num2 + 100];
                // 出现次数相同：按数值本身进行降序排序
                if (cnt1 == cnt2) {
                    return num2 - num1;
                }
                // 出现次数不同：按出现次数进行升序排列
                return cnt1 - cnt2;
            }
        });
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }
}
